#[repr(C)]
struct SortedArray {
    data: *mut SortedArrayValue,
    length: u32,
    _alloced: u32,
    equ_func: SortedArrayEqualFunc,
    cmp_func: SortedArrayCompareFunc,
}
type SortedArrayValue = *mut std::ffi::c_void;
type SortedArrayEqualFunc = fn(SortedArrayValue, SortedArrayValue) -> i32;
type SortedArrayCompareFunc = fn(SortedArrayValue, SortedArrayValue) -> i32;
fn sortedarray_first_index(
    sortedarray: &SortedArray,
    data: SortedArrayValue,
    mut left: u32,
    mut right: u32,
) -> u32 {
    let mut index = left;
    while left < right {
        index = (left + right) / 2;
        let order = (sortedarray.cmp_func)(data, sortedarray.data[index as usize]);
        if order > 0 {
            left = index + 1;
        } else {
            right = index;
        }
    }
    index
}
fn sortedarray_last_index(
    sortedarray: &SortedArray,
    data: SortedArrayValue,
    left: u32,
    right: u32,
) -> u32 {
    let mut left = left;
    let mut right = right;
    let mut index = right;
    while left < right {
        index = (left + right) / 2;
        let order = (sortedarray.cmp_func)(data, unsafe { *sortedarray.data.add(index as usize) });
        if order <= 0 {
            left = index + 1;
        } else {
            right = index;
        }
    }
    index
}
fn sortedarray_get(array: &SortedArray, i: u32) -> Option<&SortedArrayValue> {
    if array.data.is_null() {
        return None;
    }
    Some(unsafe { &*array.data.add(i as usize) })
}
fn sortedarray_length(array: &SortedArray) -> u32 {
    array.length
}
fn sortedarray_new(
    length: u32,
    equ_func: SortedArrayEqualFunc,
    cmp_func: SortedArrayCompareFunc,
) -> *mut SortedArray {
    if equ_func.is_none() || cmp_func.is_none() {
        return null_mut();
    }
    let mut length = length;
    if length == 0 {
        length = 16;
    }
    let array_layout = Layout::array::<SortedArrayValue>(length as usize).expect("Invalid layout");
    let array = unsafe { alloc(array_layout) } as *mut SortedArrayValue;
    if array.is_null() {
        return null_mut();
    }
    let sortedarray_layout = Layout::new::<SortedArray>();
    let sortedarray = unsafe { alloc(sortedarray_layout) } as *mut SortedArray;
    if sortedarray.is_null() {
        unsafe {
            let array_layout = Layout::array::<SortedArrayValue>(length as usize).unwrap();
            drop_in_place(array);
            std::alloc::dealloc(array as *mut u8, array_layout);
        }
        return null_mut();
    }
    unsafe {
        (*sortedarray).data = array;
        (*sortedarray).length = 0;
        (*sortedarray)._alloced = length;
        (*sortedarray).equ_func = equ_func;
        (*sortedarray).cmp_func = cmp_func;
    }
    sortedarray
}
fn sortedarray_free(sortedarray: *mut SortedArray) {
    unsafe {
        if !sortedarray.is_null() {
            free((*sortedarray).data as *mut libc::c_void);
            free(sortedarray as *mut libc::c_void);
        }
    }
}
fn sortedarray_remove(sortedarray: &mut SortedArray, index: u32) {
    sortedarray_remove_range(sortedarray, index, 1);
}
fn sortedarray_remove_range(sortedarray: &mut SortedArray, index: u32, length: u32) {
    if index > sortedarray.length || index + length > sortedarray.length {
        return;
    }
    unsafe {
        std::ptr::copy(
            sortedarray.data.add((index + length) as usize),
            sortedarray.data.add(index as usize),
            (sortedarray.length - (index + length)) as usize,
        );
    }
    sortedarray.length -= length;
}
fn sortedarray_insert(sortedarray: &mut SortedArray, data: SortedArrayValue) -> i32 {
    let mut left = 0;
    let mut right = sortedarray.length as usize;
    let mut index = 0;
    right = if right > 1 { right } else { 0 };
    while left != right {
        index = (left + right) / 2;
        let order = (sortedarray.cmp_func)(data, unsafe { *sortedarray.data.add(index) });
        if order < 0 {
            right = index;
        } else if order > 0 {
            left = index + 1;
        } else {
            break;
        }
    }
    if sortedarray.length > 0
        && (sortedarray.cmp_func)(data, unsafe { *sortedarray.data.add(index) }) > 0
    {
        index += 1;
    }
    if (sortedarray.length + 1) > sortedarray._alloced {
        let newsize = sortedarray._alloced * 2;
        let data = unsafe {
            libc::realloc(
                sortedarray.data as *mut libc::c_void,
                std::mem::size_of::<SortedArrayValue>() * newsize as usize,
            )
        } as *mut SortedArrayValue;
        if data.is_null() {
            return 0;
        } else {
            sortedarray.data = data;
            sortedarray._alloced = newsize;
        }
    }
    unsafe {
        std::ptr::copy(
            sortedarray.data.add(index),
            sortedarray.data.add(index + 1),
            (sortedarray.length as usize - index),
        );
    }
    unsafe {
        *sortedarray.data.add(index) = data;
    }
    sortedarray.length += 1;
    1
}
fn sortedarray_index_of(sortedarray: &SortedArray, data: SortedArrayValue) -> i32 {
    if sortedarray.is_none() {
        return -1;
    }
    let (mut left, mut right, mut index) = (0u32, sortedarray.length, 0u32);
    right = if right > 1 { right } else { 0 };
    while left != right {
        index = (left + right) / 2;
        let order =
            (sortedarray.cmp_func)(data, unsafe { *sortedarray.data.offset(index as isize) });
        if order < 0 {
            right = index;
        } else if order > 0 {
            left = index + 1;
        } else {
            left = sortedarray_first_index(sortedarray, data, left, index);
            right = sortedarray_last_index(sortedarray, data, index, right);
            for index in left..=right {
                if (sortedarray.equ_func)(data, unsafe { *sortedarray.data.offset(index as isize) })
                {
                    return index as i32;
                }
            }
            return -1;
        }
    }
    -1
}
fn sortedarray_clear(sortedarray: &mut SortedArray) {
    sortedarray.length = 0;
}
